package com.fw.leetcode.slidingwindow;

import com.fw.leetcode.LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 187. Repeated DNA Sequences
 *
 * The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
 *
 * For example, "ACGAATTCCG" is a DNA sequence.
 * When studying DNA, it is useful to identify repeated sequences within the DNA.
 *
 * Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings)
 * that occur more than once in a DNA molecule. You may return the answer in any order.
 *
 * Example 1:
 *  Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 *  Output: ["AAAAACCCCC","CCCCCAAAAA"]
 *
 * Example 2:
 *  Input: s = "AAAAAAAAAAAAA"
 *  Output: ["AAAAAAAAAA"]
 *
 * Constraints:
 *  1 <= s.length <= 10^5
 *  s[i] is either 'A', 'C', 'G', or 'T'.
 */
public class Num_0187 implements LeetCode {
    private interface Solution {
        List<String> findRepeatedDnaSequences(String s);

        default void assertEquals(String s, String[] expected) {
            List<String> result = findRepeatedDnaSequences(s);
            if (result == null || result.size() != expected.length) {
                findRepeatedDnaSequences(s);
            }
            for (int i = 0; i < result.size(); i++) {
                if (!result.get(i).equals(expected[i])) {
                    findRepeatedDnaSequences(s);
                }
            }
        }
    }

    private static class MyWindowSolution implements Solution {

        final static HashMap<Character, Integer> CHAR_CODE = new HashMap<>();
        {
            CHAR_CODE.put('A', 0x0); // 00
            CHAR_CODE.put('C', 0x1); // 01
            CHAR_CODE.put('G', 0x2); // 10
            CHAR_CODE.put('T', 0x3); // 11
        }
        @Override
        public List<String> findRepeatedDnaSequences(String s) { // 哈希表 + 滑动窗口(字符位编码)：时O(n) 空O(n)
            /*
             * 重复的DNA序列（重复出现的10字母序列）
             * - 哈希表 + 滑动窗口（需要一个能流入流出的窗口容器）
             * - ACGT 元素仅在4个元素中出现，可2位编码存储，用Int低20位存10个字符序列
             *
             * "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
             * "AAAAACCCCC""AAAAACCCCC"
             *      "CCCCCAAAAA""CCCCCAAAAA"
             * [0,1,2,3,4,5] k=2
             */
            List<String> result = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            int k = 10; // 序列固定长度
            int subWindow = 0; // 窗口容器（10字符序列编码）
            for (int i = 0; i < s.length(); i++) { // 注意边界
                subWindow = (subWindow << 2) & 0xfffff | CHAR_CODE.get(s.charAt(i)); // 窗口头流出尾流入
                if (i < k - 1) {
                    continue;
                }
                if (map.containsKey(subWindow)) {
                    map.put(subWindow, map.get(subWindow) + 1);
                    if (map.get(subWindow) == 2) { // 避免多次重复加入
                        result.add(s.substring(i-k+1, i+1)); // 注意边界
                    }
                } else {
                    map.put(subWindow, 1);
                }
            }
            return result;
        }
    }

    private static class MyHashSolution implements Solution {

        @Override
        public List<String> findRepeatedDnaSequences(String s) { // 哈希表：时O(nk) 空O(nk)
            /*
             * 重复的DNA序列（重复出现的10字母序列）
             * - 哈希表
             * "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
             * "AAAAACCCCC""AAAAACCCCC"
             *      "CCCCCAAAAA""CCCCCAAAAA"
             */
            List<String> result = new ArrayList<>();
            HashMap<String, Integer> map = new HashMap<>();
            int k = 10; // 序列固定长度
            for (int i = 0; i <= s.length() - k; i++) { // 注意边界
                String sub = s.substring(i, i + k);
                if (map.containsKey(sub)) {
                    map.put(sub, map.get(sub) + 1);
                    if (map.get(sub) == 2) { // 避免多次重复加入
                        result.add(sub);
                    }
                } else {
                    map.put(sub, 1);
                }
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyWindowSolution();
        solution.assertEquals("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", new String[]{"AAAAACCCCC","CCCCCAAAAA"});
        solution.assertEquals("AAAAAAAAAAAAA", new String[]{"AAAAAAAAAA"});
        solution.assertEquals("AAAAAAAAAAA", new String[]{"AAAAAAAAAA"});
    }
}
